package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class ShellSort {

  public static void main(String[] args) {
    // int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };

    // 创建要给80000个的随机的数组
    int[] arr = new int[8000000];
    for (int i = 0; i < 8000000; i++) {
      arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    }

    System.out.println("排序前");
    Date data1 = new Date();
    SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String date1Str = simpleDateFormat.format(data1);
    System.out.println("排序前的时间是=" + date1Str);

    // shellSort(arr); //交换式
    shellSort(arr); // 移位方式

    Date data2 = new Date();
    String date2Str = simpleDateFormat.format(data2);
    System.out.println("排序前的时间是=" + date2Str);

    // System.out.println(Arrays.toString(arr));
  }

  /*
  希尔排序：根据gap将数组分成n组，每个组内进行逻辑 插入排序
  每一轮 gap = gap/2, 直到 gap = 1,即对整个数组插入排序，终止

  gap 初始值一般为 len/2, 怎么根据gap分组：假设有 1 2 3 4 5 6 7 8, gap = 8/2 = 4
  那么1-5,2-6,3-7,4-8四组, 即每个元素(下标index)和 index-4,index+4位置上的元素为一组
  每个组排序后， gap = 2: 1-3-5-7,2-4-6-8 两组........
   */
  public static void shellSort(int[] arr) {

    // 增量gap, 并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
      // 从第gap个元素，逐个对其所在的组进行直接插入排序
      // 第gap个元素一定是第一组的第二个元素，其实有多个组时，这个循环同时交替对每个组进行插入排序
      for (int i = gap; i < arr.length; i++) {
        int j = i;
        int temp = arr[j];
        if (arr[j] < arr[j - gap]) { // 注意组内的上一个的真实下标！！
          while (j - gap >= 0 && temp < arr[j - gap]) {
            // 移动
            arr[j] = arr[j - gap];
            j -= gap;
          }
          // 此时 j 就是待插入的位置
          arr[j] = temp;
        }
      }
    }
  }
}
